{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 1-1: PLA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we use an artificial data set to study PLA. The data set is in https://www.csie.ntu.edu.tw/~htlin/course/ml15fall/hw1/hw1_15_train.dat\n",
    "\n",
    "Each line of the data set contains one (x n ,y n ) with x n ∈ R 4 . The first 4 numbers of the line contains\n",
    "the components of x n orderly, the last number is y n . Please initialize your algorithm with w = 0 and\n",
    "take sign(0) as −1. As a friendly reminder, remember to add x 0 = 1 as always!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. Implement a version of PLA by visiting examples in the na¨ıve cycle using the order of examples in the data set. Run the algorithm on the data set. What is the number of updates before the algorithm halts? **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load the dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from loadfile import *\n",
    "from PerceptronLinearAlgorithm import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "X_data, Y_data = loadfile('./data/hw1_15_train.dat')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.97681 ,  0.10723 ,  0.64385 ,  0.29556 ],\n",
       "       [ 0.67194 ,  0.2418  ,  0.83075 ,  0.42741 ],\n",
       "       [ 0.20619 ,  0.23321 ,  0.81004 ,  0.98691 ],\n",
       "       ..., \n",
       "       [ 0.93895 ,  0.93941 ,  0.72496 ,  0.95655 ],\n",
       "       [ 0.046136,  0.94413 ,  0.038311,  0.26812 ],\n",
       "       [ 0.072491,  0.2242  ,  0.62592 ,  0.67238 ]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 1.,  1.,  1.,  1.,  1.,  1., -1.,  1., -1., -1.,  1.,  1.,  1.,\n",
       "       -1., -1.,  1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "       -1.,  1.,  1., -1., -1.,  1.,  1., -1.,  1.,  1., -1., -1.,  1.,\n",
       "       -1., -1.,  1., -1.,  1.,  1.,  1., -1., -1.,  1.,  1.,  1.,  1.,\n",
       "        1.,  1.,  1.,  1.,  1., -1., -1.,  1., -1.,  1., -1., -1.,  1.,\n",
       "       -1.,  1., -1., -1.,  1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1., -1.,  1.,  1.,  1., -1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,\n",
       "        1.,  1.,  1., -1.,  1., -1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,\n",
       "       -1.,  1.,  1.,  1.,  1., -1.,  1., -1.,  1.,  1., -1.,  1.,  1.,\n",
       "        1.,  1., -1.,  1., -1., -1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1., -1., -1.,  1.,  1., -1.,  1., -1.,  1.,  1.,  1., -1.,  1.,\n",
       "       -1., -1.,  1., -1., -1.,  1.,  1.,  1.,  1., -1.,  1.,  1.,  1.,\n",
       "        1.,  1.,  1.,  1.,  1., -1., -1., -1.,  1., -1.,  1., -1.,  1.,\n",
       "       -1.,  1.,  1., -1., -1.,  1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1.,  1., -1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,  1., -1.,  1.,\n",
       "        1.,  1.,  1.,  1.,  1., -1., -1., -1., -1.,  1., -1.,  1.,  1.,\n",
       "       -1.,  1., -1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1., -1.,  1.,\n",
       "       -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1., -1.,\n",
       "        1., -1.,  1.,  1., -1.,  1.,  1.,  1.,  1., -1.,  1., -1.,  1.,\n",
       "        1.,  1.,  1.,  1., -1.,  1., -1.,  1.,  1.,  1., -1., -1.,  1.,\n",
       "        1.,  1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1., -1.,  1.,  1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1.,  1.,  1.,  1.,  1.,  1.,  1., -1.,  1., -1.,  1.,  1.,  1.,\n",
       "       -1., -1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1., -1.,\n",
       "        1.,  1.,  1., -1.,  1.,  1., -1., -1., -1.,  1.,  1., -1., -1.,\n",
       "        1., -1., -1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1., -1.,\n",
       "        1.,  1.,  1.,  1., -1.,  1.,  1., -1., -1.,  1., -1.,  1.,  1.,\n",
       "       -1.,  1.,  1.,  1.,  1.,  1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1.,  1., -1.,  1.,  1.,  1., -1.,  1., -1.,  1.,  1.,  1., -1.,\n",
       "        1.,  1.,  1., -1., -1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,\n",
       "        1.,  1., -1.,  1., -1.,  1., -1.,  1., -1.,  1.])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Y_data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Data preprocess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Add bias\n",
    "X_data = np.hstack((np.ones((X_data.shape[0],1)), X_data))\n",
    "# weights initialization\n",
    "W = np.zeros(X_data.shape[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.      ,  0.97681 ,  0.10723 ,  0.64385 ,  0.29556 ],\n",
       "       [ 1.      ,  0.67194 ,  0.2418  ,  0.83075 ,  0.42741 ],\n",
       "       [ 1.      ,  0.20619 ,  0.23321 ,  0.81004 ,  0.98691 ],\n",
       "       ..., \n",
       "       [ 1.      ,  0.93895 ,  0.93941 ,  0.72496 ,  0.95655 ],\n",
       "       [ 1.      ,  0.046136,  0.94413 ,  0.038311,  0.26812 ],\n",
       "       [ 1.      ,  0.072491,  0.2242  ,  0.62592 ,  0.67238 ]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.,  0.,  0.,  0.,  0.])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "W"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "PLA iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "37\n"
     ]
    }
   ],
   "source": [
    "PLA = pla()\n",
    "halt = PLA.pla_1(X_data, Y_data)\n",
    "print(halt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Implement a version of PLA by visiting examples in fixed, pre-determined random cycles\n",
    "throughout the algorithm. Run the algorithm on the data set. Please repeat your experiment for\n",
    "2000 times, each with a different random seed. What is the average number of updates before the\n",
    "algorithm halts?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34.2895\n"
     ]
    }
   ],
   "source": [
    "halt, accuracy = PLA.pla_2(X_data, Y_data)\n",
    "print(halt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** 3. Implement a version of PLA by visiting examples in fixed, pre-determined random cycles throughout the algorithm, while changing the update rule to be:**\n",
    "\n",
    "$$W_{t+1}\\rightarrow W_t+\\eta y_{n(t)}x_{n(t)}$$\n",
    "\n",
    "**with $\\eta=0.5$. Note that your PLA in the previous problem corresponds to $\\eta=1$. Please repeat your experiment for 2000 times, each with a different random seed. What is the average number of updates before the algorithm halts? **"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34.2895\n"
     ]
    }
   ],
   "source": [
    "halt, accuracy = PLA.pla_3(X_data, Y_data)\n",
    "print(halt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 1-2: Pocket PLA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we play with the pocket algorithm. Modify your PLA in Problem 16 to visit examples purely randomly, and then add the ‘pocket’ steps to the algorithm. We will use https://www.csie.ntu.edu.tw/~htlin/course/ml15fall/hw1/hw1_18_train.dat as the training data set D, and https://www.csie.ntu.edu.tw/~htlin/course/ml15fall/hw1/hw1_18_test.dat as the test set for “verifying” the g returned by your algorithm (see lecture 4 about verifying). The sets are of the same format as the previous one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. Run the pocket algorithm with a total of 50 updates on D, and verify the performance of w pocket using the test set. Please repeat your experiment for 2000 times, each with a different random seed. What is the average error rate on the test set? **"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load the dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# train data\n",
    "X_train, Y_train = loadfile('./data/hw1_18_train.dat')\n",
    "# test data\n",
    "X_test, Y_test = loadfile('./data/hw1_18_test.dat')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Data preprocess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Add bias\n",
    "X_train = np.hstack((np.ones((X_train.shape[0],1)), X_train))\n",
    "X_test = np.hstack((np.ones((X_test.shape[0],1)), X_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.      ,  0.94544 ,  0.42842 ,  0.79833 ,  0.16244 ],\n",
       "       [ 1.      ,  0.85365 ,  0.084168,  0.5682  ,  0.49221 ],\n",
       "       [ 1.      ,  0.17095 ,  0.82127 ,  0.98444 ,  0.51486 ],\n",
       "       ..., \n",
       "       [ 1.      ,  0.078827,  0.3823  ,  0.13965 ,  0.82677 ],\n",
       "       [ 1.      ,  0.92288 ,  0.86313 ,  0.22939 ,  0.92214 ],\n",
       "       [ 1.      ,  0.50315 ,  0.41884 ,  0.026094,  0.91623 ]])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.      ,  0.62926 ,  0.32783 ,  0.010417,  0.73102 ],\n",
       "       [ 1.      ,  0.32368 ,  0.61439 ,  0.42097 ,  0.025626],\n",
       "       [ 1.      ,  0.15968 ,  0.83346 ,  0.97515 ,  0.32762 ],\n",
       "       ..., \n",
       "       [ 1.      ,  0.34445 ,  0.30929 ,  0.049222,  0.49242 ],\n",
       "       [ 1.      ,  0.040789,  0.28334 ,  0.55817 ,  0.60612 ],\n",
       "       [ 1.      ,  0.36302 ,  0.34961 ,  0.12651 ,  0.54315 ]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pocket PLA iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.287786\n"
     ]
    }
   ],
   "source": [
    "PocketPLA = pocket_pla()\n",
    "error_mean = PocketPLA.pocket_pla_1(X_train, Y_train, X_test, Y_test)\n",
    "print(error_mean)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Modify your algorithm to return $w_{50}$(the PLA vector after 50 updates) instead of w (the pocket vector) after 50 updates. Run the modified algorithm on D, and verify the performance using the test set. Please repeat your experiment for 2000 times, each with a different random seed. What is the average error rate on the test set? Compare your result to the previous problem and briefly discuss your findings.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.300748\n"
     ]
    }
   ],
   "source": [
    "error_mean = PocketPLA.pocket_pla_2(X_train, Y_train, X_test, Y_test)\n",
    "print(error_mean)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3. Modify your algorithm in Problem 18 to run for 100 updates instead of 50, and verify the performance of w pocket using the test set. Please repeat your experiment for 2000 times, each with a different random seed. What is the average error rate on the test set?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.287875\n"
     ]
    }
   ],
   "source": [
    "error_mean = PocketPLA.pocket_pla_3(X_train, Y_train, X_test, Y_test)\n",
    "print(error_mean)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
